<!DOCTYPE html>
<html lang="zh">
  <head>
    <meta charset="UTF-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>快速排序：完整数组状态演示</title>
    <style>
      * {
        box-sizing: border-box;
        margin: 0;
        padding: 0;
      }

      body {
        font-family: 'Segoe UI', Tahoma, Geneva, Verdana, sans-serif;
        background: linear-gradient(135deg, #1a2a6c, #b21f1f, #1a2a6c);
        color: white;
        text-align: center;
        padding: 20px;
        min-height: 100vh;
      }

      .container {
        max-width: 1000px;
        margin: 0 auto;
        background: rgba(0, 0, 0, 0.7);
        border-radius: 15px;
        padding: 25px;
        box-shadow: 0 10px 30px rgba(0, 0, 0, 0.5);
      }

      h1 {
        font-size: 2.8rem;
        margin-bottom: 10px;
        text-shadow: 0 2px 4px rgba(0, 0, 0, 0.5);
        color: #ffcc00;
      }

      .subtitle {
        font-size: 1.2rem;
        margin-bottom: 25px;
        color: #ddd;
      }

      .array-container {
        background: rgba(30, 30, 50, 0.7);
        border-radius: 10px;
        padding: 20px;
        margin: 20px 0;
        box-shadow: inset 0 0 15px rgba(0, 0, 0, 0.3);
      }

      .array-row {
        display: flex;
        justify-content: center;
        margin: 15px 0;
        flex-wrap: wrap;
      }

      .element {
        width: 50px;
        height: 50px;
        line-height: 50px;
        margin: 5px;
        text-align: center;
        border-radius: 8px;
        font-weight: bold;
        font-size: 1.2rem;
        color: white;
        transition: all 0.4s cubic-bezier(0.175, 0.885, 0.32, 1.275);
        box-shadow: 0 4px 8px rgba(0, 0, 0, 0.3);
        transform: translateY(0);
      }

      .element:hover {
        transform: translateY(-5px);
        box-shadow: 0 8px 15px rgba(0, 0, 0, 0.4);
        z-index: 10;
      }

      .pivot {
        background: linear-gradient(135deg, #ff9a00, #ff6a00);
        border: 2px solid #ffcc00;
      }

      .left {
        background: linear-gradient(135deg, #3498db, #2980b9);
        border: 2px solid #2ecc71;
      }

      .right {
        background: linear-gradient(135deg, #2ecc71, #27ae60);
        border: 2px solid #3498db;
      }

      .merged {
        background: linear-gradient(135deg, #9b59b6, #8e44ad);
        border: 2px solid #f1c40f;
      }

      .waiting {
        background: linear-gradient(135deg, #7f8c8d, #95a5a6);
        border: 2px solid #bdc3c7;
      }

      .base {
        background: linear-gradient(135deg, #e74c3c, #c0392b);
        border: 2px solid #ff9f43;
      }

      .controls {
        display: flex;
        justify-content: center;
        gap: 15px;
        margin: 20px 0;
        flex-wrap: wrap;
      }

      button {
        padding: 12px 25px;
        margin: 5px;
        font-size: 1.1rem;
        font-weight: bold;
        border: none;
        border-radius: 50px;
        cursor: pointer;
        transition: all 0.3s;
        background: linear-gradient(135deg, #3498db, #2980b9);
        color: white;
        box-shadow: 0 4px 8px rgba(0, 0, 0, 0.3);
      }

      button:hover {
        transform: translateY(-3px);
        box-shadow: 0 6px 12px rgba(0, 0, 0, 0.4);
      }

      button:active {
        transform: translateY(1px);
      }

      button:disabled {
        opacity: 0.5;
        cursor: not-allowed;
        transform: none;
      }

      #play-btn {
        background: linear-gradient(135deg, #2ecc71, #27ae60);
      }

      #reset-btn {
        background: linear-gradient(135deg, #e74c3c, #c0392b);
      }

      #log {
        margin: 20px auto;
        min-height: 60px;
        font-size: 1.3rem;
        padding: 15px;
        background: rgba(40, 40, 60, 0.8);
        border-radius: 10px;
        max-width: 800px;
        box-shadow: 0 4px 8px rgba(0, 0, 0, 0.2);
        display: flex;
        align-items: center;
        justify-content: center;
      }

      .legend {
        display: flex;
        justify-content: center;
        gap: 20px;
        margin: 25px 0;
        flex-wrap: wrap;
      }

      .legend-item {
        display: flex;
        align-items: center;
        gap: 8px;
        font-size: 1rem;
      }

      .color-box {
        width: 20px;
        height: 20px;
        border-radius: 4px;
        display: inline-block;
        border: 1px solid rgba(255, 255, 255, 0.3);
      }

      .progress-container {
        width: 100%;
        height: 10px;
        background: rgba(255, 255, 255, 0.1);
        border-radius: 5px;
        margin: 20px 0;
        overflow: hidden;
      }

      .progress-bar {
        height: 100%;
        background: linear-gradient(90deg, #ff9a00, #ff6a00);
        border-radius: 5px;
        transition: width 0.3s;
      }

      .step-indicator {
        display: flex;
        justify-content: space-between;
        margin: 10px 0 25px;
        font-weight: bold;
        color: #ffcc00;
      }

      .algorithm-info {
        text-align: left;
        margin: 25px auto;
        padding: 15px;
        background: rgba(40, 40, 60, 0.6);
        border-radius: 10px;
        max-width: 800px;
      }

      .algorithm-info h3 {
        color: #ffcc00;
        margin-bottom: 10px;
        text-align: center;
      }

      .algorithm-info p {
        margin-bottom: 10px;
        line-height: 1.6;
      }

      .history-container {
        margin-top: 20px;
        max-height: 300px;
        overflow-y: auto;
        border: 1px solid #444;
        border-radius: 8px;
        padding: 10px;
        background: rgba(20, 20, 30, 0.7);
      }

      .history-title {
        font-size: 1.2rem;
        margin-bottom: 10px;
        color: #ffcc00;
      }

      .history-step {
        margin: 8px 0;
        padding: 8px;
        background: rgba(60, 60, 80, 0.5);
        border-radius: 6px;
        text-align: left;
      }

      .history-array {
        display: flex;
        margin-top: 5px;
      }

      .history-element {
        width: 30px;
        height: 30px;
        line-height: 30px;
        margin: 2px;
        text-align: center;
        border-radius: 5px;
        font-size: 0.9rem;
      }

      @media (max-width: 768px) {
        .element {
          width: 40px;
          height: 40px;
          line-height: 40px;
          font-size: 1rem;
        }

        h1 {
          font-size: 2.2rem;
        }

        .subtitle {
          font-size: 1rem;
        }

        button {
          padding: 10px 20px;
          font-size: 1rem;
        }
      }

      @media (max-width: 480px) {
        .element {
          width: 35px;
          height: 35px;
          line-height: 35px;
        }

        h1 {
          font-size: 1.8rem;
        }

        .legend {
          gap: 10px;
        }

        .legend-item {
          font-size: 0.9rem;
        }
      }
    </style>
  </head>
  <body>
    <div class="container">
      <h1>快速排序：完整数组状态演示</h1>
      <p class="subtitle">每一步都展示完整数组状态，直观理解快速排序过程</p>

      <div class="array-container">
        <div id="timeline"></div>
      </div>

      <div class="progress-container">
        <div id="progress" class="progress-bar"></div>
      </div>

      <div class="step-indicator">
        <span id="current-step">步骤: 0</span>
        <span id="total-steps">总步骤: 0</span>
      </div>

      <div class="controls">
        <button id="prev-btn" onclick="prevStep()">上一步</button>
        <button id="play-btn" onclick="togglePlay()">播放</button>
        <button id="next-btn" onclick="nextStep()">下一步</button>
        <button id="reset-btn" onclick="reset()">重置</button>
      </div>

      <div id="log">点击"下一步"开始排序</div>

      <div class="legend">
        <div class="legend-item"><span class="color-box pivot"></span> Pivot (基准)</div>
        <div class="legend-item"><span class="color-box left"></span> Left (小于基准)</div>
        <div class="legend-item"><span class="color-box right"></span> Right (大于等于基准)</div>
        <div class="legend-item"><span class="color-box merged"></span> 合并完成</div>
        <div class="legend-item"><span class="color-box waiting"></span> 待处理</div>
        <div class="legend-item"><span class="color-box base"></span> Base (基本情况)</div>
      </div>

      <div class="history-container">
        <div class="history-title">排序历史记录</div>
        <div id="history"></div>
      </div>

      <div class="algorithm-info">
        <h3>快速排序算法说明</h3>
        <p>快速排序是一种分而治之的排序算法：</p>
        <p>1. 选择一个元素作为"基准"（pivot）</p>
        <p>2. 将数组分为两个子数组：小于基准的元素和大于等于基准的元素</p>
        <p>3. 递归地对两个子数组进行快速排序</p>
        <p>4. 合并结果：左子数组 + 基准 + 右子数组</p>
        <p>平均时间复杂度：O(n log n) | 最坏情况：O(n²)</p>
      </div>
    </div>

    <script>
      const original = [10, 17, 22, 8, 13, 9, 3, 7, 1, 8, 5, 2]
      let steps = []
      let currentStep = 0
      let autoPlayInterval = null
      let isPlaying = false
      let historySteps = []

      // 生成动画步骤
      function generateSteps(arr) {
        steps = []
        historySteps = []
        const n = arr.length

        function buildLayer(logicalArr, highlightsMap) {
          return logicalArr.map((val, idx) => {
            return {
              value: val,
              status: highlightsMap[idx] || 'waiting'
            }
          })
        }

        function helper(arr) {
          if (arr.length <= 1) {
            const layer = buildLayer(arr, { 0: 'base' })
            const msg = `基本情况：子数组长度为1 (${arr.join(', ')})`
            steps.push({ layer, msg })
            historySteps.push({ array: [...arr], msg, type: 'base' })
            return arr
          }

          const pivot = arr[0]
          const leftArr = arr.slice(1).filter((x) => x < pivot)
          const rightArr = arr.slice(1).filter((x) => x >= pivot)

          const highlights = {}
          arr.forEach((val, i) => {
            if (i === 0) highlights[i] = 'pivot'
            else if (leftArr.includes(val)) highlights[i] = 'left'
            else highlights[i] = 'right'
          })

          const partitionMsg = `划分数组：基准值=${pivot}，左子数组=[${leftArr}], 右子数组=[${rightArr}]`
          steps.push({
            layer: buildLayer(arr, highlights),
            msg: partitionMsg
          })
          historySteps.push({ array: [...arr], msg: partitionMsg, type: 'partition' })

          const sortedLeft = helper(leftArr)
          const sortedRight = helper(rightArr)

          const merged = [...sortedLeft, pivot, ...sortedRight]
          const mergedHighlights = {}
          merged.forEach((_, i) => (mergedHighlights[i] = 'merged'))

          const mergeMsg = `合并结果：[${sortedLeft}] + ${pivot} + [${sortedRight}] = [${merged}]`
          steps.push({
            layer: buildLayer(merged, mergedHighlights),
            msg: mergeMsg
          })
          historySteps.push({ array: [...merged], msg: mergeMsg, type: 'merge' })

          return merged
        }

        helper(arr)

        // 添加初始状态
        const initMsg = '初始数组：点击"下一步"开始排序'
        steps.unshift({
          layer: buildLayer(arr, {}),
          msg: initMsg
        })
        historySteps.unshift({ array: [...arr], msg: initMsg, type: 'init' })

        // 添加最终状态
        const sortedArray = [...arr].sort((a, b) => a - b)
        const sortedMsg = '✅ 排序完成！数组已完全有序'
        steps.push({
          layer: buildLayer(sortedArray, {}),
          msg: sortedMsg
        })
        historySteps.push({ array: sortedArray, msg: sortedMsg, type: 'complete' })

        // 更新总步骤显示
        document.getElementById('total-steps').textContent = `总步骤: ${steps.length - 1}`

        // 更新历史记录
        updateHistory()
      }

      // 更新历史记录
      function updateHistory() {
        const historyContainer = document.getElementById('history')
        historyContainer.innerHTML = ''

        historySteps.forEach((step, index) => {
          const historyStep = document.createElement('div')
          historyStep.className = 'history-step'

          const stepType =
            index === 0
              ? '初始状态'
              : step.type === 'partition'
              ? '划分'
              : step.type === 'base'
              ? '基本情况'
              : step.type === 'merge'
              ? '合并'
              : index === historySteps.length - 1
              ? '完成'
              : '步骤'

          historyStep.innerHTML = `
                    <div><strong>${index + 1}. ${stepType}:</strong> ${step.msg}</div>
                    <div class="history-array">
                        ${step.array
                          .map(
                            (val) =>
                              `<div class="history-element" 
                                  style="background: ${getColorByValue(val, step.array)}">${val}</div>`
                          )
                          .join('')}
                    </div>
                `

          historyContainer.appendChild(historyStep)
        })

        // 滚动到底部
        historyContainer.scrollTop = historyContainer.scrollHeight
      }

      // 根据值获取颜色
      function getColorByValue(value, array) {
        if (array.length <= 1) return 'linear-gradient(135deg, #e74c3c, #c0392b)'

        const pivot = array[0]
        if (value === pivot) return 'linear-gradient(135deg, #ff9a00, #ff6a00)'

        const pivotIndex = array.indexOf(pivot)
        const leftArr = array.slice(0, pivotIndex).filter((x) => x < pivot)
        const rightArr = array.slice(0, pivotIndex).filter((x) => x >= pivot)

        if (leftArr.includes(value)) return 'linear-gradient(135deg, #3498db, #2980b9)'
        if (rightArr.includes(value)) return 'linear-gradient(135deg, #2ecc71, #27ae60)'
        if (value > pivot) return 'linear-gradient(135deg, #9b59b6, #8e44ad)'

        return 'linear-gradient(135deg, #7f8c8d, #95a5a6)'
      }

      // 渲染当前步骤
      function renderStep(stepIndex) {
        const container = document.getElementById('timeline')
        container.innerHTML = ''

        const step = steps[stepIndex]
        if (!step) return

        const row = document.createElement('div')
        row.className = 'array-row'

        step.layer.forEach((item) => {
          const el = document.createElement('div')
          el.className = `element ${item.status}`
          el.innerText = item.value
          row.appendChild(el)
        })

        container.appendChild(row)
        document.getElementById('log').innerText = step.msg

        // 更新当前步骤显示
        document.getElementById('current-step').textContent = `步骤: ${stepIndex}`

        // 更新进度条
        const progress = (stepIndex / (steps.length - 1)) * 100
        document.getElementById('progress').style.width = `${progress}%`

        // 更新按钮状态
        document.getElementById('prev-btn').disabled = stepIndex === 0
        document.getElementById('next-btn').disabled = stepIndex === steps.length - 1

        // 更新历史记录高亮
        updateHistoryHighlight(stepIndex)
      }

      // 更新历史记录高亮
      function updateHistoryHighlight(stepIndex) {
        const historySteps = document.querySelectorAll('.history-step')
        historySteps.forEach((step, index) => {
          if (index === stepIndex) {
            step.style.background = 'rgba(80, 80, 120, 0.8)'
            step.style.border = '2px solid #ffcc00'
          } else {
            step.style.background = 'rgba(60, 60, 80, 0.5)'
            step.style.border = 'none'
          }
        })
      }

      // 下一步
      function nextStep() {
        if (currentStep < steps.length - 1) {
          currentStep++
          renderStep(currentStep)
        }
      }

      // 上一步
      function prevStep() {
        if (currentStep > 0) {
          currentStep--
          renderStep(currentStep)
        }
      }

      // 播放/暂停
      function togglePlay() {
        if (isPlaying) {
          clearInterval(autoPlayInterval)
          document.getElementById('play-btn').textContent = '播放'
          isPlaying = false
        } else {
          autoPlayInterval = setInterval(() => {
            if (currentStep < steps.length - 1) {
              nextStep()
            } else {
              clearInterval(autoPlayInterval)
              document.getElementById('play-btn').textContent = '播放'
              isPlaying = false
            }
          }, 1500)
          document.getElementById('play-btn').textContent = '暂停'
          isPlaying = true
        }
      }

      // 重置
      function reset() {
        clearInterval(autoPlayInterval)
        isPlaying = false
        document.getElementById('play-btn').textContent = '播放'
        currentStep = 0
        generateSteps(original)
        renderStep(currentStep)
      }

      // 初始化
      window.onload = function () {
        generateSteps(original)
        renderStep(currentStep)
      }
    </script>
  </body>
</html>
